Divisor Counting Function
The divisor counting function (or just divisor function) \(d : \mathbb{Z}^+ \to \mathbb{Z}^+\) is a function which counts the number of positive divisors of the input.
Often this function is instead denoted by \(\tau\).
Suppose \(n\) has unique factorisation into a product of primes \(p_1^{\alpha_1} \dots p_k^{\alpha_k}\). Then
Proof
This is a counting problem. If \(n = p_1^{\alpha_1} \dots p_k^{\alpha_k}\) then factors are of the form \(p_1^{\beta_1} \dots p_k^{\beta_k}\) where \(\beta_i \leq \beta_j\) as per divisibility from unique factorisations. Each possible value of each \(\beta_i\) defines a unique factor and for each \(i\), \(\beta_i \in \{0, \dots, \alpha_i\}\) which means there are \(\alpha_i + 1\) possible values.
Hence we have
We can also express the divisor counting function as a Dirichlet convolution.
\(d\) is multiplicative. That is, for \(m, n \in \mathbb{Z}\) with \(m\) and \(n\) coprime integers
Proof
Let \(n = p_1^{\alpha_1} \dots p_k^{\alpha_k}\) and \(m = q_1^{\beta_1} \dots q_s^{\beta_s}\). If \(\gcd(m, n) = 1\), then \(p_i \neq q_j\) for all \(i, j\). Therefore \(nm = p_1^{\alpha_1} \dots p_k^{\alpha_k} q_1^{\beta_1} \dots q_s^{\beta_s}\) is the unique factorisation into a product of primes without duplicate primes.
As such we have